字符串 |
您所在的位置：网站首页 › 求最长重复子串的长度 ckmp › 字符串 |
字符串
|
题目：给定一个字符串，求最长重复子串，这两个子串不能重叠。例如，str = "acdcdcdcd"，则不可重叠的最长子串为"cdcd"。 思路：二分枚举+height数组分组。这道题的思想很巧妙，后面要仔细推敲。先二分答案，把题目变成判定性问题：判断是否存在两个长度为k的子串是相同的，且不重叠。解决这个问题的关键还是利用height数组。把排序后的后缀分成若干组，其中每组的后缀之间的height值都不小于k。例如，字符串为“aabaaaab”，当k=2时，后缀分成了4组，如图所示。 容易看出，有希望成为最长公共前缀不小于k的两个后缀一定在同一组。然后对于每组后缀，只须判断每个后缀的sa值的最大值和最小值之差是否不小于k。如果有一组满足，则说明存在，否则不存在。整个做法的时间复杂度为O(nlogn)。 代码： 1 public class MaxRepeatSubString2 { 2 3 public static void main(String[] args) { 4 int res = maxRepeatSubString2("1x23231923263"); 5 System.out.println(res); // 输出 3 6 } 7 8 /** 9 * 不允许交叉 10 * 11 * @param src 12 * @return 13 */ 14 public static int maxRepeatSubString2(String src) { 15 SuffixArray.Suff[] sa = SuffixArray.getSa2(src); 16 int[] height = SuffixArray.getHeight(src, sa); 17 int l = 0; 18 int r = height.length; 19 int ans = 0; 20 while (l > 1);// check的重叠长度 22 if (check(height, sa, mid)) { 23 if (mid == height.length / 2) { 24 return mid; 25 } 26 l = mid + 1; 27 ans = mid; 28 // return mid; 29 } else { 30 r = mid - 1; 31 } 32 } 33 return ans; 34 } 35 36 /** 37 * 用len将height分组,小于组和大于等于组交替 38 * 在大于组中更新最大最小原始小标,大转小的时候检查上一个大于组是否满足不重叠 39 * 在小于组中,只需持续地将原始下标付给max和min,这样小转大的时候,可以保留小于组最后一个元素的下标 40 */ 41 private static boolean check(int []height,SuffixArray.Suff[]sa,int len){ 42 int minIndex = sa[0].index; 43 int maxIndex = sa[0].index; 44 for(int i = 1;i=len){ // lcp 大于 len 47 minIndex = Math.min(minIndex,index); 48 maxIndex = Math.max(maxIndex, index); 49 } else { 50 if (maxIndex - minIndex >= len) { 51 return true; 52 } 53 maxIndex = index; 54 minIndex = index; 55 } 56 } 57 return (maxIndex - minIndex) >= len; 58 } 59 60 } 在此基础上稍加改动可以完成至少出现K次的最长重复子串(可重叠)的题目 本文来自博客园，作者：|旧市拾荒|，转载请注明原文链接：https://www.cnblogs.com/xiaoyh/p/10328219.html |
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |